package sort;

import java.util.Arrays;

/**
 * Created by luoqifei on 2017/7/16.
 */
public class QuickSort {
    public int partition(int[] arr,int low,int high){

        int base = arr[low];
        while (low<high){
            //从右开始往左遍历，小于基数的数据放最左边
            while (base<arr[high] && low<high){
                high--;
            }
            arr[low] = arr[high];
            while (base > arr[low] && low<high){
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = base;
        return low;
    }
    public int[] quickSort(int[] numbers,int low,int high){
        if(numbers.length>0){
            if(low<high){
                int middle = partition(numbers,low,high);
                quickSort(numbers,low,middle-1);
                quickSort(numbers,middle+1,high);
            }
        }
        return numbers;
    }
    public static void main(String[] args) {
        int[] a = {2,1,6,32,5,3,4,78,54,99,35,0};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
}
